package cn.collin.lbs;


/**
 * @author collin.code@gmail.com
 * 
 */
public class PointPolygon {
	final double INFINITY = 1e10;
	final double ESP = 1e-5;
	final int MAX_N = 1000;

	public boolean isIn(Point point, Point[] polygon) {
		int n = polygon.length;
		int count = 0;
		Point point2 = new Point();
		point2.y = point.y;
		point2.x = -INFINITY;
		Line line = new Line(point,point2);
		
		for (int i = 0; i < n; i++) {
			// �õ�����ε�һ���
			Line side = new Line();
			side.point1 = polygon[i];
			side.point2 = polygon[(i + 1) % n];
			if (IsOnline(point, side)) {
				return true;
			}

			// ���sideƽ��x��������
			if (Math.abs(side.point1.y - side.point2.y) < ESP) {
				continue;
			}

			if (IsOnline(side.point1, line)) {
				if (side.point1.y > side.point2.y) {
					count++;
				}
			} else if (IsOnline(side.point2, line)) {
				if (side.point2.y > side.point1.y) {
					count++;
				}
			} else if (Intersect(line, side)) {
				count++;
			}
		}
		if (count % 2 == 1) {
			return true;
		} else {
			return false;
		}
	}

	private boolean IsOnline(Point point, Line line) {
		return ((Math.abs(Multiply(line.point1, line.point2, point)) < ESP) &&

		((point.x - line.point1.x) * (point.x - line.point2.x) <= 0) &&

		((point.y - line.point1.y) * (point.y - line.point2.y) <= 0));
	}

	private double Multiply(Point p1, Point p2, Point p0) {
		return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y));
	}

	// �ж��߶��ཻ
	private boolean Intersect(Line L1, Line L2) {
		return ((Math.max(L1.point1.x, L1.point2.x) >= Math.min(L2.point1.x,
				L2.point2.x))
				&&

				(Math.max(L2.point1.x, L2.point2.x) >= Math.min(L1.point1.x,
						L1.point2.x))
				&&

				(Math.max(L1.point1.y, L1.point2.y) >= Math.min(L2.point1.y,
						L2.point2.y))
				&&

				(Math.max(L2.point1.y, L2.point2.y) >= Math.min(L1.point1.y,
						L1.point2.y))
				&&

				(Multiply(L2.point1, L1.point2, L1.point1)
						* Multiply(L1.point2, L2.point2, L1.point1) >= 0) &&

		(Multiply(L1.point1, L2.point2, L2.point1)
				* Multiply(L2.point2, L1.point2, L2.point1) >= 0)

		);
	}
}
